# 给定一个二叉树的根节点 root ，返回它的 中序 遍历。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：root = [1,null,2,3]
# 1
# / \
#     2
# / \
#     3
# 输出：[1,3,2]
#  
# 
#  示例 2： 
# 
#  
# 输入：root = []
# 输出：[]
#  
# 
#  示例 3： 
# 
#  
# 输入：root = [1]
# 输出：[1]
#  
# 
#  示例 4： 
# 
#  
# 输入：root = [1,2]
# 输出：[2,1]
#  
# 
#  示例 5： 
# 
#  
# 输入：root = [1,null,2]
# 输出：[1,2]
#  
# 
#  
# 
#  提示： 
# 
#  
#  树中节点数目在范围 [0, 100] 内 
#  -100 <= Node.val <= 100 
#  
# 
#  
# 
#  进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
#  Related Topics 栈 树 深度优先搜索 二叉树 
#  👍 1080 👎 0


from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []

        def inorder(node: TreeNode):
            if node is None:
                return
            inorder(node.left)
            ans.append(node.val)
            inorder(node.right)

        inorder(root)
        return ans


# leetcode submit region end(Prohibit modification and deletion)


"""
递归(推荐): 左边结果, 中间值, 右边结果;
"""


# class Solution:
#     def inorderTraversal(self, root: TreeNode) -> List[int]:
#         res = []
#
#         def inorder(r: TreeNode):
#             if r is None:
#                 return
#             inorder(r.left)
#             res.append(r.val)
#             inorder(r.right)
#
#         inorder(root)
#         return res

# 迭代
# def inorderTraversal(self, root: TreeNode) -> List[int]:
#     ans = []
#     stack = []
#     while root or stack:
#         while root:
#             stack.append(root)
#             root = root.left
#         root = stack.pop()
#         ans.append(root.val)
#         root = root.right
#     return ans


def log(*args, **kwargs):
    print(*args, **kwargs)


if __name__ == '__main__':
    s = Solution()
    t1 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    res1 = s.inorderTraversal(t1)
    e1 = [1, 2, 3]
    assert e1 == res1
